home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The 640 MEG Shareware Studio 2
/
The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO
/
pascal
/
megasort.zip
/
MEGASORT.LTG
Wrap
Text File
|
1987-10-19
|
7KB
|
268 lines
Megasort: A Distribution Sort
Listing 1
1: PROGRAM megaa; {Copyright 1986 by Steve Heller, Inc. All rights reserved.}
2:
3: CONST
4: MaxSize = 5000;
5:
6: TYPE
7: AnyString = String[255];
8: SomeString = String[10];
9: StrPtrArr = ARRAY [1..MaxSize] OF ^AnyString;
10: SortArray = ARRAY [Char] OF Integer;
11:
12: VAR
13: TestArray : ^StrPtrArr;
14: TestArray2 : ^StrPtrArr;
15: TestArray3 : ^StrPtrArr;
16: junk : AnyString;
17: i : Integer;
18: infile : text[10000];
19: infilename : AnyString;
20: outfile : text[10000];
21: outfilename : AnyString;
22: KeyLen : Integer;
23: ArrayLength : Integer;
24:
25: PROCEDURE Megasort(VAR PtrArray:StrPtrArr; VAR SubArray1:StrPtrArr;
26: VAR Subarray2:StrPtrArr;
27: ArrayCount:Integer;KeyLength:Integer;ArraySize:Integer);
28:
29: VAR
30: l : Char;
31: m : Char;
32: i : Integer;
33: j : Integer;
34: BucketCount : SortArray;
35: BucketPosition : SortArray;
36: TempPtrArr : ^StrPtrArr;
37: TempSubArr1: ^StrPtrArr;
38: TempSubArr2: ^StrPtrArr;
39:
40:
41: BEGIN
42:
43: New(TempPtrArr);
44: New(TempSubArr1);
45: New(TempSubArr2);
46:
47: FOR i := KeyLength DOWNTO 1 DO
48: BEGIN
49: FOR l := #0 TO #255 DO
50: BucketCount[l] := 0;
51: FOR j := 1 TO ArraySize DOè 52: BEGIN
53: IF i > length(PtrArray[j]^) THEN
54: m := #0
55: ELSE
56: m := PtrArray[j]^[i];
57: BucketCount[m] := BucketCount[m] + 1;
58: END;
59:
60: BucketPosition[#0] := 1;
61: FOR l := #1 TO #255 DO
62: BucketPosition[l] := BucketCount[pred(l)] + BucketPosition[pred(l)];
63:
64: FOR j := 1 TO ArraySize DO
65: BEGIN
66: IF i > length(PtrArray[j]^) THEN
67: m := #0
68: ELSE
69: m := PtrArray[j]^[i];
70: TempPtrArr^[BucketPosition[m]] := PtrArray[j];
71: IF ArrayCount >=2 THEN
72: TempSubArr1^[BucketPosition[m]] := SubArray1[j];
73: IF ArrayCount =3 THEN
74: TempSubArr2^[BucketPosition[m]] := SubArray2[j];
75: BucketPosition[m] := BucketPosition[m] + 1;
76: END;
77:
78: FOR j := 1 TO ArraySize DO
79: BEGIN
80: PtrArray[j] := TempPtrArr^[j];
81: IF ArrayCount >=2 THEN
82: SubArray1[j] := TempSubArr1^[j];
83: IF ArrayCount = 3 THEN
84: SubArray2[j] := TempSubArr2^[j];
85: END;
86:
87: END;
88:
89: Dispose(TempPtrArr);
90: Dispose(TempSubArr1);
91: Dispose(TempSubArr2);
92:
93: END;
94:
95:
96:
97:
98: BEGIN
99: New(TestArray);
100:
101: Write('Input file name: ');
102: ReadLn(infilename);
103: Write('Output file name: ');
104: ReadLn(outfilename);
105: Write('Key length: ');
106: ReadLn(KeyLen);è 107: Assign(infile,infilename);
108: Reset(infile);
109: Assign(outfile,outfilename);
110: Rewrite(outfile);
111:
112: WriteLn('Reading input file.');
113:
114: i := 0;
115: WHILE NOT EOF(infile) DO
116: BEGIN
117: i := i + 1;
118: ReadLn(infile,junk);
119: GetMem(TestArray^[i],length(junk)+1);
120: TestArray^[i]^ := junk;
121: END;
122:
123: ArrayLength := i;
124:
125: WriteLn('Sorting.');
126:
127: Megasort(TestArray^,TestArray^,TestArray^,1,KeyLen,ArrayLength);
128:
129: WriteLn('Writing output file.');
130:
131: FOR i := 1 TO ArrayLength DO
132: WriteLn(outfile,TestArray^[i]^);
133:
134: Close(infile);
135: Close(outfile);
136:
137: WriteLn('Done.');
138:
139: END.
Listing 2
Listing 2
{SORTDAT.PAS - generates sort data for MEGASORT testing}
{861223 :2200}
VAR
i,j : Integer;
ir : Real;
s : String[255];
t : Text[10000];
n : Real;
Itype : Char;
MaxLength : Integer;
Ran : Char;
RealTemp : Real;
IntTemp : Integer;
RealExp : ARRAY [-30..30] OF Real;
FName : String[80];èBEGIN
RealExp[-30] := 1E-30;
FOR i := -29 TO 30 DO
RealExp[i] := RealExp[i-1]*10;
Write('Name of data file to be generated: ');
ReadLn(FName);
Write('Number of items to generate: ');
ReadLn(n);
Write('Type of items (R for real, I for integer, S for string): ');
ReadLn(Itype);
Itype := Upcase(Itype);
IF Itype = 'S' THEN
BEGIN
Write('Maximum length of strings: ');
ReadLn(MaxLength);
Write('Random string length or all maximum length (R or M): ');
ReadLn(Ran);
Ran := Upcase(Ran);
END;
Assign(t,Fname);
Rewrite(t);
ir := 1.0;
REPEAT
BEGIN
IF ir = 1000*int(ir/1000) THEN WriteLn(ir:10:0);
IF Itype = 'S' THEN
BEGIN
s := '';
IF Ran = 'R' THEN
FOR j := 1 TO random(MaxLength) DO
s := s + chr(random(64)+32)
ELSE
FOR j := 1 TO MaxLength DO
s := s + chr(random(64)+32);
WriteLn(t,s);
END
ELSE IF Itype = 'R' THEN
BEGIN
RealTemp := Random;
IF Random > 0.5 THEN
RealTemp := -RealTemp;
IntTemp := Random(30);
RealTemp := RealTemp * RealExp[IntTemp];
Str(RealTemp,s);
IF RealTemp > 0 THEN
s := copy(s,3,length(s))
ELSE
s := copy(s,2,length(s));
WriteLn(t,s);
END
ELSE IF Itype = 'I' THEN
BEGIN
IntTemp := Random(32767);è IF Random >0.5 THEN
IntTemp := -IntTemp;
Str(IntTemp,s);
WriteLn(t,s);
END;
END;
ir := ir + 1.0;
UNTIL ir > n;
Close(t);
END.
MEGAA.PAS page 3